package airthmetic.exercise.search;

import java.util.PriorityQueue;

public class _1091_二进制矩阵中的最短路径 {
    int[][] direction = new int[][]{
            {-1, -1},
            {-1, 0},
            {-1, 1},
            {0, -1},
            {0, 1},
            {1, -1},
            {1, 0},
            {1, 1}};
    //定义网格大小
    int n;

    public int shortestPathBinaryMatrix(int[][] grid) {
        n = grid.length;
        int m = grid[0].length;
        if(grid[0][0] == 1 || grid[n-1][m-1] == 1){
            return -1;
        }

        PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>((v1, v2)->{
            return v1.f - v2.f;
        });
        queue.offer(new Vertex(0,0,grid[0][0] = 1));
        while(!queue.isEmpty()){
            Vertex v = queue.poll();
            int step = grid[v.x][v.y];
            if(v.x == n-1 && v.y == m-1){
                return step;
            }

            for(int[] dir : direction){
                int newX = v.x +dir[0];
                int newY = v.y +dir[1];
                if(newX<0 || newY<0 || newX>=n || newY>=m){
                    continue;
                }
                if (grid[newX][newY] == 0 || grid[newX][newY] > step + 1) {
                    queue.offer(new Vertex(newX, newY, grid[newX][newY] = step + 1));
                }
            }
        }

        return -1;




    }

    //定义顶点
    class Vertex{
        int x, y, f;
        public Vertex(int x, int y, int step) {
            this.x = x;
            this.y = y;
            //曼哈顿距离变体
            int diff = Math.max(n - x, n - y);
            this.f = diff + step; // 离右下角近的点优先计算 使用曼哈顿距离 并且加上当前的步数,因为有可能两个点的diff一样，但是走到这两个点的步数不一样
        }
    }
}
